Control from computer science

This paper presents some of the principles underlying verification and controller synthesis techniques for discrete dynamical systems developed within Computer Science along with some ideas to extend them to continuous and hybrid systems. Hopefully, this will provide control theorists and engineers with an additional perspective of their discipline as seen by a sympathetic outsider, uncommitted to the customs and traditions of the domain. Inter-cultural experience can be frustrating but sometimes fun.     

Vegetation establishment on the southern Israeli coastal sand dunes between the years 1965 and 1999

Since 1960, the Israeli coastal dunes have undergone a stabilization process that is manifested in the increase of vegetation cover and in a decrease in the abundance of sand-living flora and fauna species. The objective of the study was to quantify, using remote sensing and GIS, the rate and extent of vegetation expansion and their resultant temporal changes on Israel’s southern coastal dunes between the years 1965 and 1999.The results indicate that during the entire study period, the vegetation-covered area grew by 82% at an annual average growth rate of 1.75%. Concurrently, the bare shifting dune area decreased by 37% at an annual average growth rate of 1.34%.The conspicuous trend over the period studied, despite regressive processes, is a transition from bare shifting dunes to stabilized, vegetation-covered dunes. The extrapolation of the results, assuming continuation of processes and no destruction effects, indicates that with the decrease in the bare shifting dunes, the ratio of bare shifting dunes and sparse vegetation coverage landscape will equalize by between 2007 and 2010.According to this extrapolation, between 2012 and 2015, no bare shifting dune landscape will remain, and the study area will be covered with sparse- and dense-level vegetation cover. Beginning in 2035, the entire study area will be covered in vegetation whose density will be between 60 and 100%. Meso-climate and land use changes are among the factors that might explain this phenomenon.     

The Minimax and Maximin Location Problems on a Network with Uniform Distributed Weights

In this paper we consider the weighted minimax and maximin location problems on the network when the weights are drawn from a uniform distribution. In the minimax (maximin) problem with stochastic demand the probability that the maximum (minimum) weighted distance between the facility and demand points exceeding (falling short of) a given value T is minimized. Properties of the solution points for both problems are proven and algorithms are presented.     

Cryogenic scanning tunneling spectroscopy studies of inhomogeneous superconductors

We applied scanning tunneling microscopy and spectroscopy, combined with magnetic susceptibility measurements and Mossbauer spectroscopy, in studies of three superconducting materials. Two belong to a new class of high T_c magnetic-superconductor systems, R_1.4Ce_0.6RuSr₂Cu₂O_10-δ (R=Eu and Gd), which are magnetically ordered at T_N≪T_c. The third is a granular normal-superconductor system, where the superconducting phase is YNi₂B₂C. In this paper we focus on the tunneling measurements, which exhibit large spatial variations of the local electronic properties for all three materials. Albeit, these local measurements also reveal pronounced differences between the third and the first two systems, which will be discussed in view of their macroscopic properties.     

Machine identification of buds in images of plant shoots

Tissue cultures find increasingly widespread applications for cloning of many plants. Commercial propagation by tissue cultures is limited to ornamental plants, because the cost of skilled labor required cannot compete with conventional propagation methods. To cut down the cost, some automation is essential. A cost-effective approach is to chop the plantlets into segments on a conveying production line while using machine vision for identifying and locating the number and positions of propagation organs in images of the plantlet segments. Plantlet segments without propagation organs will be rejected, while segments with viable buds will be selected for subculturing. To this end, a machine-vision-controlled automatic subculturing system for potato tissue cultures is proposed as a simpler and more cost-effective solution than the popular trend of imitating the manual sub-culturing task by a robot. A simple and relatively fast image-processing algorithm particularly suitable for classification of potato tissue cultures, was developed. In lieu of the general Medial Axis Transform approach, this specialized algorithm takes advantage of the inherent difference between the geometrical shape and gray scale levels of the stems and the leaves as well as of the rather simple connectivity rules of attachment between them. The results indicate that machine inspection and classification of tissue culture plantlets is possible, but considerably more work needs to be done before this technique is fully developed for automating tissue culture processes.     

Dynamic cycle detection

This paper presents algorithms for maintaining a directed acyclic graph in a dynamically changing environment. In such an environment, nodes and edges are occasionally added and deleted. The underlying idea is to perform a depth first search after each edge addition. Heuristics are presented to make fewer and relatively short searches.The problem of maintaining a directed acyclic graph arises naturally in situations involving resource contention. In operating and database systems, one often maintains a directed ‘wait for’ graph. A cycle in such a graph indicates deadlock. Thus, the algorithm presented here is attractive for centralized continuous deadlock detection.     

Inferring Finite Automata with Stochastic Output Functions and an Application to Map Learning

It is often useful for a robot to construct a spatial representation of its environment from experiments and observations, in other words, to learn a map of its environment by exploration. In addition, robots, like people, make occasional errors in perceiving the spatial features of their environments. We formulate map learning as the problem of inferring from noisy observations the structure of a reduced deterministic finite automaton. We assume that the automaton to be learned has a distinguishing sequence. Observation noise is modeled by treating the observed output at each state as a random variable, where each visit to the state is an independent trial and the correct output is observed with probability exceeding 1/2. We assume no errors in the state transition function.Using this framework, we provide an exploration algorithm to learn the correct structure of such an automaton with probability 1 – , given as inputs , an upper bound m on the number of states, a distinguishing sequence s, and a lower bound > 1/2 on the probability of observing the correct output at any state. The running time and the number of basic actions executed by the learning algorithm are bounded by a polynomial in ^–l, m, |s|, and (1/2-)^–1.We discuss the assumption that a distinguishing sequence is given, and present a method of using a weaker assumption. We also present and discuss simulation results for the algorithm learning several automata derived from office environments.     

Lifetime measurements in an electrostatic ion beam trap using image charge monitoring

A technique for mass-selective lifetime measurements of keV ions in a linear electrostatic ion beam trap is presented. The technique is based on bunching the ions using a weak RF potential and non-destructive ion detection by a pick-up electrode. This method has no mass-limitation, possesses the advantage of inherent mass-selectivity, and offers a possibility of measuring simultaneously the lifetimes of different ion species with no need for prior mass-selection.     

On the complexity of computation in the presence of link failures: the case of a ring

Summary We investigate the message complexity of distributed computations on rings of asynchronous processors. In such computations, each processor has an initial local value and the task is to compute some predetermined function of all local values. Our work deviates from previous works concerning the complexity of ring computations in that we consider the effect oflink failures. A link is said to fail if some message sent through it never reaches its destination. We show that the message complexity of any function, which is sensitive to all its inputs, is (n logn) whenn, the number of processors, is a-priori known; and is (n ² ) whenn is not known. Interestingly, these tight bounds do not depend on whether the identity of a leader is a-priori known before the computation starts. These results stand in sharp contrast to the situation in asynchronous rings with no link failures, where the message complexity is affected by the a-priori knowledge of a leader but is not affected by the knowledge ofn. Oded Goldreich was born in Tel-Aviv, Israel, on February 4th 1957. Received B.A., M.Sc., and D.Sc. in Computer Science from the Technion — Israel Institute of Technology, Haifa, Israel, in 1980, 1982, and 1983, respectively. He is currently an Associate Professor of Computer Science in the Technion. From 1983 to 1986, he was a postdoctoral fellow in MIT's Laboratory for Computer Science. His research interests include cryptography and related areas, relation between randomness and algorithms, and distributed computation. Luiba Shrira was born in Vilnius, Lithuania. Received B.A., M.Sc., and D.Sc. in Computer Science from the Technion—Israel Institute of Technology, Haifa, Israel in 1977, 1980, and 1985, respectively. from 1986 to 1989 she was a postdoctoral fellow at Laboratory for Computer science at MIT, where she is currently a Research Associate. Her research interests include highly-available and reliable distributed algorithms and systems, persistent object systems, and programming methodology.Part of the work has been done while the first author was in the Laboratory for Computer Science of MIT and the second author was in the Computer Science Department of the Technion. First author was partially supported by a Weizmann Postdoctoral Fellowship, an IBM Postdoctoral Fellowship, and Albert Einstein Research Fund (through Technion's V.P.R. Fund)